package simple;

import java.util.Arrays;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/2/10 18:47
 */
public class No453_最小操作次数使数组元素相等 {
    public static void main(String[] args) {
        Solution453 solution453 = new Solution453();
        int[] nums = new int[]{7, 12, 4, 9};
        int i = solution453.minMoves(nums);
        System.out.println(i);
    }
}


class Solution453 {
    public int minMoves(int[] nums) {
        // 数学归纳

        //12,4,9,7
        //sum+3a=4x
        //a=x-4

        //一般化
        //sum + (nums.length-1)a = 4(a+min)
        //sum + (nums.length-1)a = nums.length*a+nums.length*min
        // a= sum - nums.length*min

        //获取最小值
        int min = Integer.MAX_VALUE;
        //数组总和
        int sum = 0;
        for (int num : nums) {
            min = Math.min(min, num);
            sum += num;
        }
        return sum - nums.length * min;
    }
}



    //public int minMoves(int[] nums) {
    //    Arrays.sort(nums);
    //    // 动态规划(排序)
    //    //dp[i]:记dp[i]为最少i+1个元素相同的时候的数组经过的最少操作次数
    //    //初始化数组dp
    //    //长度
    //    int n = nums.length;
    //    int[] dp = new int[n];
    //    //找出动态规划变化方程
    //
    //
    //
    //
    //
    //    //返回更改后添加
    //
    //    //演算  4,7,9,12
    //    //dp[0]=0
    //
    //    //dp[1] = dp[0]+nums[1]-nums[0] = 3  ;nums[2] += dp[1]
    //    //dp[2] = dp[1] + nums[2] - nums[1] ; nums[3] += dp[2]
    //    //dp[3] = dp[2] + nums[3] - nums[2]
    //    dp[0] = 0;
    //    for (int i = 1; i < n; i++) {
    //        //获取到每一层的diff
    //        //dp[i]
    //        int diff = nums[i] - nums[i - 1];
    //        //dp[i]正式
    //        dp[i] = dp[i - 1] + diff;
    //        //每层diff计算完毕,之后,要将下一层预备好,即:对nums数组元素进行更改
    //        if (i + 1 < n) {
    //            nums[i + 1] += dp[i];
    //        }
    //    }
    //    //n是数组长度
    //    return dp[n - 1];
    //}



    //public int minMoves(int[] nums) {
    //    // 规律排序
    //    Arrays.sort(nums);
    //    int sum = 0;
    //    for (int i = 1; i < nums.length; i++) {
    //        sum += nums[i];
    //    }
    //    return sum - (nums.length - 1) * nums[0];
    //}







